1. Field of the Invention
The present invention is directed to accessing and maintaining arrays of data elements. It particularly concerns elements of arrays whose sizes can be changed dynamically.
2. Background Information
In computer programming, it is often convenient to refer to a plurality of data objects as a group, or array. For example, the array may be referred to as MyArray, whereas its first and fourth elements may be referred to as MyArray[0] and MyArray[3].
Most often, the array's size is assigned at the outset, and a block of memory space suitable for containing an array of that size is allocated. The array may be allocated statically, i.e., when the program is initially loaded, or dynamically, i.e., at a point in the program's execution at which it is determined that the array will be needed. Even though the program allocates the array dynamically, the array's size may be fixed when that allocation occurs.
But there are programs in which it is inconvenient to restrict arrays to fixed sizes. The array's ultimate needed size may be unknown but potentially very large when the array is initially allocated, and it may be wasteful to allocate the maximum possible array size initially. In such situations, programs often implement “growable” arrays.
A well-known approach to doing so is as follows. When the program determines that the array needs to include more elements than the memory so far allocated to it can hold, it allocates space twice as large as the array's previous space, copies the current contents into the new space's first half, and then adds new elements to the new space's second half, possibly initializing the second-half contents in the process. Pointers to the array are then adjusted to refer to the array's new location.
This approach has become popular, because it enables the program to avoid allocating space of the maximum size when an array that may never grow to that size is initially allocated. But it has certain disadvantages, a principal one of which manifests itself in multi-threaded programs, in which multiple concurrently executing threads may seek access to the same array. There are many situations in which it is difficult or impossible to insure that the program will behave correctly if one thread's access to the array occurs concurrently with another thread's copying expansion of that array. So multi-threaded programs often need to employ locks: when a thread is performing a copying expansion on an array, it prevents other threads from accessing the array. Such locking reduces performance and affects scalability adversely. It may also reduce a system's fault tolerance, and it can cause priority inversion in real-time systems.